package com.algrithom.dp;

/**
 * 813. 最大平均值和的分组
 */
public class Solution8 {
    
    public static void main(String[] args){
        int[] array = new int[]{9,1,2,3,9};
        Solution8 solution8 = new Solution8();
        System.out.println(solution8.largestSumOfAverages2(array,3));
    }
    
    public double largestSumOfAverages(int[] A,int K){
        int len = A.length;
        double[] preSum = new double[len + 1];
        for (int i = 0; i < len; ++i) {
            preSum[i + 1] = preSum[i] + A[i];
        }
        
        double[] dp = new double[len + 1];
        for (int i = 1; i <= len; ++i) {
            dp[i] = preSum[i] / i;
        }
        
        for (int k = 0; k < K - 1; ++k) {
            for (int i = 1; i <= len; ++i) {
                for (int j = 0; j < i; ++j) {
                    dp[i] = Math.max(dp[i],(preSum[i] - preSum[j]) / (i - j) + dp[j]);
                }
            }
        }
        return dp[len];
    }
    
    double largestSumOfAverages2(int[] array,int K){
        int len = array.length;
        if (len == 0) {
            return 0.0;
        }
        
        double[] prefixSum = new double[len + 1];
        for (int i = 1; i <= len; i++) {
            prefixSum[i] = prefixSum[i - 1] + array[i - 1];
        }
        
        double[][] dp = new double[len + 1][K + 1];
        
        for (int i = 1; i <= len; i++) {
            dp[i][1] = prefixSum[i] / i;
        }
        
        for (int i = 2; i <= len; i++) {
            for (int k = 2; k <= K; k++) {
                for (int j = 0; j < i; j++) {
                    dp[i][k] = Math.max(dp[i][k],dp[j][k - 1] + (prefixSum[i] - prefixSum[j]) / (i - j));
                }
            }
        }
        
        return dp[len][K];
    }
}